/**
 * //给定一棵树的前序遍历 preorder 与中序遍历 inorder。请构造二叉树并返回其根节点。
 * //
 * //
 * //
 * // 示例 1:
 * //
 * //
 * //Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
 * //Output: [3,9,20,null,null,15,7]
 * //
 * //
 * // 示例 2:
 * //
 * //
 * //Input: preorder = [-1], inorder = [-1]
 * //Output: [-1]
 * //
 * //
 * //
 * //
 * // 提示:
 * //
 * //
 * // 1 <= preorder.length <= 3000
 * // inorder.length == preorder.length
 * // -3000 <= preorder[i], inorder[i] <= 3000
 * // preorder 和 inorder 均无重复元素
 * // inorder 均出现在 preorder
 * // preorder 保证为二叉树的前序遍历序列
 * // inorder 保证为二叉树的中序遍历序列
 * //
 * // Related Topics 树 数组 哈希表 分治 二叉树 👍 1311 👎 0
 */

package com.xixi.dataStructure.tree.binaryTree;

import com.xixi.dataStructure.tree.TreeNode;

public class ID00105ConstructBinaryTreeFromPreorderAndInorderTraversal {
    public static void main(String[] args) {
        Solution solution = new ID00105ConstructBinaryTreeFromPreorderAndInorderTraversal().new Solution();
    }


//leetcode submit region begin(Prohibit modification and deletion)

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode() {}
     *     TreeNode(int val) { this.val = val; }
     *     TreeNode(int val, TreeNode left, TreeNode right) {
     *         this.val = val;
     *         this.left = left;
     *         this.right = right;
     *     }
     * }
     */
    class Solution {
        int[] p = {3,9,20,15,7};
        int[] i = {9,3,15,20,7};

        public Solution(){
            buildTree(p, i);
        }

        public TreeNode buildTree(int[] preorder, int[] inorder) {
            if (preorder == null || inorder == null) return null;

            return assembleChildrenTrees(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
        }

        /*
         * @Desc:
         * @Author vincentML
         * @Date: 2021/12/1 10:24
         * @param root 当前节点的指针
         * @param preorder 前序遍历数组
         * @param pFrom 当前树由前序遍历的数组下标 pFrom - pTo 组成
         * @param pTo
         * @param inorder 中序遍历数组
         * @param iFrom 当前树由中序遍历的数组下标 iFrom - iTo 组成
         * @param iTo
         * @return com.xixi.dataStructure.tree.TreeNode
         */
        public TreeNode assembleChildrenTrees( int[] preorder, int pFrom, int pTo, int[] inorder, int iFrom, int iTo) {
            if(pFrom ==pTo && iFrom == iTo) return  new TreeNode(preorder[pFrom]);
            //先通过前序遍历的第一个节点找到父节点
            TreeNode root = new TreeNode(preorder[pFrom]);

            //再通过中序遍历区分左右子树
            int j = 0;
            while(inorder[iFrom +j] != preorder[pFrom] && j <= iTo){//preorder 和 inorder 均无重复元素, 所以找到相等元素的时候遍可以停止
                ++j;
            }
            //preorder中 (pFrom+1) - (pFrom + j) 是左子树，(pFrom + j+1) - pTo 是右子树。
            //inorder中 iFrom - (iFrom + (j-1) 是左子树，(j+1) - iTo 是右子树
            if( 1<= j ){ //pFrom+1 <= pFrom + j  && iFrom < iFrom + j -1 才有左子树
                root.left = assembleChildrenTrees(preorder, pFrom+1, pFrom + j, inorder, iFrom, iFrom + j-1);
            }
            if((pFrom + j + 1) <= pTo && (iFrom + j+1) <= iTo ){ //(j+1) <= pTo 才有右子树
                root.right = assembleChildrenTrees(preorder, pFrom + j + 1, pTo, inorder, iFrom + j+1, iTo);
            }

            return root;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)


}